﻿#pragma once

#include<assert.h>
enum Color
{
	RED,
	BLACK
};

//  红黑树的性质
// 1. 每个结点不是红色就是黑色 
// 2. 根节点是黑色的 
// 3. 如果一个节点是红色的，则它的两个孩子结点是黑色的 
// 4. 对于每个结点，从该结点到其所有后代叶结点的简单路径上，均 包含相同数目的黑色结点 
// 5. 每个叶子结点都是黑色的(此处的叶子结点指的是空结点)
template<class K, class V>
struct RBTreeNode
{
	RBTreeNode<K, V>* _left;
	RBTreeNode<K, V>* _right;
	RBTreeNode<K, V>* _parent;
	pair<K, V> _kv;

	int _bf;
	Color _col;
	RBTreeNode(const pair<K, V>& kv)
		:_left(nullptr)
		, _right(nullptr)
		, _parent(nullptr)
		, _kv(kv)
		, _bf(0)
		, _col(Color)
	{}
};

template<class K, class V>
class RBTree
{
	typedef RBTreeNode<K, V> Node;
public:
	bool Insert(const pair<K, V>& kv)
	{
		if (_root == nullptr)
		{
			_root = new Node(kv);
			_root->_col = BLACK;
			return true;
		}
		else
		{
			// 由于插入黑色节点会影响整个树的结构，所以一般插入都是红色节点
			// 插入红色节点存在两种情况，一：父节点是黑色节点，不需要改变，即插入结束
			//                           二：父节点是红色节点，需要改变（改变又分为两种：1——只需要改变颜色）
			//                                                                           2——旋转+改变颜色）
		}
	}
private:
	Node* _root = nullptr;
};